package org.yao.datastructure.stack;

/**
 * @author yaoxiang29703
 * @since 2021/4/9
 */
public class ArrayStackDemo {
    public static void main(String[] args) {
        Calculator calculator = new Calculator();
        String expression = "8/2+3-6/3";
        int res = calculator.calculate(expression);
        System.out.println(expression + "=" + res);

    }
}

/**
 * 计算器
 */
class Calculator {
    /**
     * 存放数字的栈
     */
    private ArrayStack numStack;
    /**
     * 存放操作符的栈
     */
    private ArrayStack operaStack;

    public Calculator() {
        numStack = new ArrayStack(10);
        operaStack = new ArrayStack(10);
    }

    /**
     * 获取操作符的优先级
     *
     * @param opera
     * @return
     */
    @SuppressWarnings("all")
    public int getPriority(int opera) {
        if (opera == '*' || opera == '/') {
            return 1;
        } else if (opera == '+' || opera == '-') {
            return 0;
        } else {
            throw new RuntimeException("输入操作符有误");
        }
    }

    /**
     * 计算
     *
     * @param num1
     * @param num2
     * @param opera
     * @return
     */
    private int doCalculate(int num1, int num2, int opera) {
        int res = 0;
        switch (opera) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                // 注意顺序
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                // 注意顺序
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }

    /**
     * 判断字符是否是操作符
     *
     * @param c
     * @return
     */
    public boolean isOpera(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    /**
     * 计算表达式
     *
     * @param expression 算术表达式 “3+5*2-4”
     * @return
     */
    public int calculate(String expression) {
        // 遍历expression每个字符
        char c = ' ';
        int num1, num2, opera, res;
        for (int i = 0; i < expression.length(); i++) {
            c = expression.charAt(i);
            if (isOpera(c)) {
                // 如果是运算符，分三种情况
                // 1.操作符栈为空，直接入栈
                if (operaStack.isEmpty()) {
                    operaStack.add(c);
                    continue;
                }
                // 2.当前运算符的优先级小于等于操作符栈顶元素优先级
                if (getPriority(c) <= getPriority(operaStack.peek())) {
                    // 取出数栈的前两个元素和操作符栈的栈顶元素做运算
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    opera = operaStack.pop();
                    res = doCalculate(num1, num2, opera);
                    // 计算结果入数栈,
                    numStack.add(res);
                    // 当前操作符入操作符栈
                    operaStack.add(c);
                } else {
                    // 3、当前运算符的优先级大于操作符栈顶元素优先级，直接入符号栈
                    operaStack.add(c);
                }
            } else {
                // 数字直接入数字栈，注意char类型‘1’ 对应数值是49
                numStack.add(c - 48);
            }
        }
        // 依次从数栈中取出两个数，操作符栈取出一个操作符进行运算，运算结果压入数栈，然后再重复，直到操作符栈为空
        while (!operaStack.isEmpty()) {
            // 取出数栈的前两个元素和操作符栈的栈顶元素做运算
            num1 = numStack.pop();
            num2 = numStack.pop();
            opera = operaStack.pop();
            res = doCalculate(num1, num2, opera);
            // 计算结果入数栈,
            numStack.add(res);
        }
        return numStack.pop();
    }

}

class ArrayStack {
    /**
     * 栈顶
     */
    private int top;
    /**
     * 栈的大小
     */
    private int size;
    /**
     * 栈的元素
     */
    private int[] data;

    public ArrayStack(int size) {
        this.size = size;
        data = new int[size];
        top = -1;
    }

    public void add(int num) {
        if (isFull()) {
            System.out.println("栈已满");
        }
        top++;
        data[top] = num;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈已空");
        }
        int res = data[top];
        top--;
        return res;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈已空");
        }
        return data[top];
    }

    public boolean isFull() {
        return top == size - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }
}